{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #找到字符串中所有字母异位词"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findAnagrams"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到字符串中所有字母异位词"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个字符串&nbsp;<code>s</code>&nbsp;和<b>&nbsp;</b><code>p</code>，找到&nbsp;<code>s</code><strong>&nbsp;</strong>中所有 <code>p</code> 的&nbsp;<strong>变位词&nbsp;</strong>的子串，返回这些子串的起始索引。不考虑答案输出的顺序。</p>\n",
    "\n",
    "<p><strong>变位词 </strong>指字母相同，但排列不同的字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = &quot;cbaebabacd&quot;, p = &quot;abc&quot;\n",
    "<strong>输出: </strong>[0,6]\n",
    "<strong>解释:</strong>\n",
    "起始索引等于 0 的子串是 &quot;cba&quot;, 它是 &quot;abc&quot; 的变位词。\n",
    "起始索引等于 6 的子串是 &quot;bac&quot;, 它是 &quot;abc&quot; 的变位词。\n",
    "</pre>\n",
    "\n",
    "<p><strong>&nbsp;示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = &quot;abab&quot;, p = &quot;ab&quot;\n",
    "<strong>输出: </strong>[0,1,2]\n",
    "<strong>解释:</strong>\n",
    "起始索引等于 0 的子串是 &quot;ab&quot;, 它是 &quot;ab&quot; 的变位词。\n",
    "起始索引等于 1 的子串是 &quot;ba&quot;, 它是 &quot;ab&quot; 的变位词。\n",
    "起始索引等于 2 的子串是 &quot;ab&quot;, 它是 &quot;ab&quot; 的变位词。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length, p.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code>&nbsp;和 <code>p</code> 仅包含小写字母</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>注意：本题与主站 438&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/\" style=\"background-color: rgb(255, 255, 255);\">https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [VabMRr](https://leetcode.cn/problems/VabMRr/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [VabMRr](https://leetcode.cn/problems/VabMRr/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        # 字符串、哈希表、滑动窗口\n",
    "        # 本题和567题思路完全一样\n",
    "        from collections import Counter\n",
    "        need = Counter(p)\n",
    "        left, right = 0, len(p) - 1\n",
    "        lst = []\n",
    "        while right < len(s):\n",
    "            window = Counter(s[left: right + 1])\n",
    "            if need == window:\n",
    "                lst.append(left)\n",
    "            left += 1\n",
    "            right += 1\n",
    "        return lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        check = Counter(p)\n",
    "        ans = []\n",
    "        for index in range(len(s) - len(p) + 1):\n",
    "            if check == Counter(s[index:index + len(p)]):\n",
    "                ans.append(index)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        m, n = len(s), len(p)\n",
    "        if m < n:\n",
    "            return []\n",
    "        cha_dict = collections.defaultdict(int)\n",
    "        for i in range(n):\n",
    "            cha_dict[p[i]] += 1\n",
    "        ans = list()\n",
    "        for i in range(n):\n",
    "            cha_dict[s[i]] -= 1\n",
    "            if cha_dict[s[i]] == 0:\n",
    "                cha_dict.pop(s[i])\n",
    "        if not cha_dict:\n",
    "            ans.append(0)\n",
    "        for i in range(n, m):\n",
    "            cha_dict[s[i - n]] += 1\n",
    "            cha_dict[s[i]] -= 1\n",
    "            if cha_dict[s[i]] == 0:\n",
    "                cha_dict.pop(s[i])\n",
    "            if cha_dict[s[i - n]] == 0:\n",
    "                cha_dict.pop(s[i - n])\n",
    "            if not cha_dict:\n",
    "                ans.append(i - n + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        if len(s) < len(p):\n",
    "            return []\n",
    "\n",
    "        # 遍历p\n",
    "        start_index_ls = []\n",
    "        count_d = {}\n",
    "        for pi in p:\n",
    "            count_d[pi] = count_d.get(pi, 0) + 1\n",
    "        \n",
    "        # 遍历s\n",
    "        max_d = copy.copy(count_d)\n",
    "        diff_count = len(p)\n",
    "        for si in s[:len(p)]:\n",
    "            if si in count_d:\n",
    "                count_d[si] -= 1\n",
    "                if count_d[si] >= 0:\n",
    "                    diff_count -= 1\n",
    "        \n",
    "        if diff_count == 0:\n",
    "            start_index_ls.append(0)\n",
    "        for index in range(len(p), len(s)):\n",
    "            si = s[index - len(p)]\n",
    "            if si in count_d:\n",
    "                count_d[si] += 1\n",
    "                if 0 < count_d[si] <= max_d[si]:\n",
    "                    diff_count += 1\n",
    "            si = s[index]\n",
    "            if si in count_d:\n",
    "                count_d[si] -= 1\n",
    "                if count_d[si] >= 0:\n",
    "                    diff_count -= 1\n",
    "            if diff_count == 0:\n",
    "                start_index_ls.append(index - len(p) + 1)\n",
    "        return start_index_ls\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        m=len(s)\n",
    "        n=len(p)\n",
    "        if m<n:\n",
    "            return []\n",
    "        \n",
    "        dic1={}\n",
    "        for i in range(n):\n",
    "            char =p[i]\n",
    "            if char in dic1:\n",
    "                dic1[char]+=1\n",
    "            else:\n",
    "                dic1[char]=1\n",
    "        \n",
    "        chars=list(dic1.keys())\n",
    "        res=[]\n",
    "        dic2={}\n",
    "        for i in range(m):\n",
    "            char=s[i]\n",
    "            if char not in  chars:\n",
    "                continue \n",
    "            \n",
    "            if char in dic2:\n",
    "                dic2[char].append(i)\n",
    "            else:\n",
    "                dic2[char]=[i]\n",
    "            \n",
    "            if len(dic1)==len(dic2):\n",
    "                temp_list=[]\n",
    "                flag=False \n",
    "                for char in chars:\n",
    "                    if len(dic2[char])<dic1[char]:\n",
    "                        flag=True\n",
    "                        break \n",
    "                    temp_list.extend(dic2[char][-dic1[char]:])\n",
    "                if flag:\n",
    "                    continue \n",
    "                a=min(temp_list)\n",
    "                b=max(temp_list)\n",
    "                if b-a+1==n:\n",
    "                    res.append(a)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        m = len(p)\n",
    "        ans = []\n",
    "        test = sorted(p)\n",
    "        for i in range(n-m+1):\n",
    "            if sorted(s[i:i+m]) == test:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        dic1 = {pp:0 for pp in p}\n",
    "        dic2 = {}\n",
    "        for pp in p:\n",
    "            if pp not in dic2:\n",
    "                dic2[pp] = 1\n",
    "            else:\n",
    "                dic2[pp] += 1\n",
    "        ans = []\n",
    "        def judge(dic1,dic2):\n",
    "            for key in dic1:\n",
    "                if dic1[key] < dic2[key]:\n",
    "                    return False\n",
    "            return True\n",
    "        cur_len = 0\n",
    "        left = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in dic1:\n",
    "                dic1[s[i]] += 1\n",
    "            cur_len += 1\n",
    "            if cur_len >= len(p):\n",
    "                if judge(dic1,dic2):\n",
    "                    ans.append(left)\n",
    "                if s[left] in dic1:\n",
    "                    dic1[s[left]] -= 1\n",
    "                left+=1\n",
    "                cur_len -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        arr1, arr2 = [0]*26, [0]*26\n",
    "        n = len(p)\n",
    "        res = []\n",
    "        for i in p:\n",
    "            arr1[ord(i) - ord('a')] += 1\n",
    "        for i in range(len(s)):\n",
    "            arr2[ord(s[i]) - ord('a')] += 1\n",
    "            if i >= n-1:\n",
    "                if arr1 == arr2:\n",
    "                    res.append(i-n+1)\n",
    "                arr2[ord(s[i-n+1]) - ord('a')] -= 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        # 字符串、哈希表、滑动窗口\n",
    "        # 本题和567题思路完全一样\n",
    "        from collections import Counter\n",
    "        need = Counter(p)\n",
    "        left, right = 0, len(p) - 1\n",
    "        lst = []\n",
    "        while right < len(s):\n",
    "            window = Counter(s[left: right + 1])\n",
    "            if need == window:\n",
    "                lst.append(left)\n",
    "            left += 1\n",
    "            right += 1\n",
    "        return lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        if len(s) < len(p):\n",
    "            return []\n",
    "        dicp = {}\n",
    "        res = []\n",
    "        for i in p:\n",
    "            dicp[i] = dicp.get(i, 0) + 1\n",
    "        start = 0\n",
    "        end = 0\n",
    "        dics = {}\n",
    "        while end < len(s):\n",
    "            dics[s[end]] = dics.get(s[end], 0) + 1\n",
    "            if dics[s[end]] > dicp.get(s[end], 0):\n",
    "                for i in range(start, end + 1):\n",
    "                    dics[s[i]] -= 1\n",
    "                    if s[i] == s[end]:\n",
    "                        break\n",
    "                start = i + 1\n",
    "                end = end + 1\n",
    "            elif end - start + 1 == len(p):\n",
    "                res.append(start)\n",
    "                dics[s[start]] -= 1\n",
    "                start += 1\n",
    "                end += 1\n",
    "            else:\n",
    "                end += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        m,n = len(s),len(p)\n",
    "        cnt = Counter(p)\n",
    "        res = []\n",
    "        for i in range(m-n+1):\n",
    "            if Counter(s[i:i+n])==cnt:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        res = []\n",
    "        needs = collections.defaultdict(int)\n",
    "        for i in p:\n",
    "            needs[i] += 1\n",
    "        l = 0\n",
    "        cnt = collections.defaultdict(int)\n",
    "        for r in range(len(s)):\n",
    "            if s[r] in needs:\n",
    "                cnt[s[r]] += 1\n",
    "            if r-l+1 == len(p):\n",
    "                if needs == cnt:\n",
    "                    res.append(l)\n",
    "                if s[l] in cnt:\n",
    "                    cnt[s[l]] -= 1\n",
    "                l += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"class Solution:\n",
    "    # 超时\n",
    "    # 字符串变位词，字符串字串，出现相同字母的数量相同\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        m = len(s)\n",
    "        n = len(p)\n",
    "        res = []\n",
    "        cnt1 = [0] * 26\n",
    "        for i in p:\n",
    "            cnt1[ord(i) - ord('a')] += 1\n",
    "        for j in range(0, m-n+1):\n",
    "            cnt2 = [0] * 26\n",
    "            k = j+n\n",
    "            for l in s[j:k]:\n",
    "                 cnt2[ord(l) - ord('a')] += 1\n",
    "            if cnt1 == cnt2:\n",
    "                res.append(j)\n",
    "        return res\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        s_len, p_len = len(s), len(p)\n",
    "        if s_len < p_len:\n",
    "            return []\n",
    "        res = []\n",
    "        s_count = [0]*26\n",
    "        p_count = [0]*26\n",
    "        for i in range(p_len):\n",
    "            p_count[ord(p[i]) - ord('a')] += 1\n",
    "            s_count[ord(s[i]) - ord('a')] += 1\n",
    "        if s_count == p_count:\n",
    "            res.append(0)\n",
    "        for i in range(0, s_len - p_len):\n",
    "            s_count[ord(s[i]) -ord('a')] -= 1\n",
    "            s_count[ord(s[i + p_len]) - ord('a')] += 1\n",
    "            if s_count == p_count:\n",
    "                res.append(i+1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s, p):\n",
    "        s_len, p_len = len(s), len(p)\n",
    "        \n",
    "        if s_len < p_len:\n",
    "            return []\n",
    "\n",
    "        ans = []\n",
    "        s_count = [0] * 26\n",
    "        p_count = [0] * 26\n",
    "        for i in range(p_len):\n",
    "            s_count[ord(s[i]) - 97] += 1\n",
    "            p_count[ord(p[i]) - 97] += 1\n",
    "\n",
    "        if s_count == p_count:\n",
    "            ans.append(0)\n",
    "\n",
    "        for i in range(s_len - p_len):\n",
    "            s_count[ord(s[i]) - 97] -= 1\n",
    "            s_count[ord(s[i + p_len]) - 97] += 1\n",
    "            \n",
    "            if s_count == p_count:\n",
    "                ans.append(i + 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        n=len(p)\n",
    "        need=collections.Counter(p)\n",
    "        cnt=len(p)\n",
    "        result=[]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in p:\n",
    "                if need[s[i]]>0:\n",
    "                    cnt-=1\n",
    "                need[s[i]]-=1\n",
    "            left=i-len(p)#不加一是为了使第一个点起作用\n",
    "            if left>=0:\n",
    "                if s[left] in p:\n",
    "                    if need[s[left]]>=0:\n",
    "                        cnt+=1\n",
    "                    need[s[left]]+=1\n",
    "            if cnt==0:\n",
    "                result.append(i-len(p)+1)\n",
    "        return result\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        # 滑动窗口\n",
    "        # 用数组储存代替哈希表\n",
    "        n = len(p)\n",
    "        m = len(s)\n",
    "        if m < n:\n",
    "            return []\n",
    "        \n",
    "        res = []\n",
    "        cnt = [0] * 26\n",
    "        for string in p:\n",
    "            cnt[ord(string) - ord(\"a\")] += 1\n",
    "\n",
    "        check = [0] * 26                                #初始化check\n",
    "        for i in range(n):\n",
    "            check[ord(s[i]) - ord(\"a\")] += 1\n",
    "        if check == cnt:\n",
    "                res.append(0)\n",
    "        # 开始滑窗\n",
    "        for right in range(n, m):\n",
    "            left =  right - n\n",
    "            check[ord(s[right]) - ord(\"a\")] += 1\n",
    "            check[ord(s[left]) - ord(\"a\")] -= 1\n",
    "            if check == cnt:\n",
    "                res.append(left + 1)\n",
    "        \n",
    "        return res\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "        \n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        need = {}\n",
    "        win = {}\n",
    "        for w in p:\n",
    "            if w not in need:\n",
    "                need[w] = 1\n",
    "                win[w] = 0\n",
    "            else:\n",
    "                need[w] += 1\n",
    "        \n",
    "        l, r = 0, 0\n",
    "        v = 0\n",
    "        res = []\n",
    "\n",
    "        while r < n:\n",
    "            c = s[r]\n",
    "            r += 1\n",
    "\n",
    "            if c in need:\n",
    "                win[c] += 1\n",
    "                if win[c] == need[c]:\n",
    "                    v += 1\n",
    "            \n",
    "            while r-l >= len(p):\n",
    "                if v == len(need):\n",
    "                    res.append(l)\n",
    "\n",
    "                d = s[l]\n",
    "                l += 1\n",
    "                if d in need:\n",
    "                    if win[d] == need[d]:\n",
    "                        v -= 1\n",
    "                    win[d] -= 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "\n",
    "        length_A = len(s)\n",
    "        length_B = len(p)\n",
    "        res = []\n",
    "        arr_A = [0]*26\n",
    "        arr_B = [0]*26\n",
    "        if length_B> length_A:\n",
    "            return res\n",
    "        \n",
    "        for i in range(length_B):\n",
    "            arr_B[ord(p[i]) - ord('a')] += 1\n",
    "            arr_A[ord(s[i]) - ord('a')] += 1\n",
    "\n",
    "        if arr_A == arr_B:\n",
    "            res.append(0)\n",
    "        \n",
    "        for j in range(length_B, length_A):\n",
    "            arr_A[ord(s[j]) - ord('a')] += 1\n",
    "            arr_A[ord(s[j - length_B]) - ord('a')] -= 1\n",
    "            if arr_B == arr_A:\n",
    "                res.append(j - length_B + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        res = []\n",
    "        n = len(s)\n",
    "        m = len(p)\n",
    "        if n < m:\n",
    "            return res \n",
    "        cnt = collections.Counter(p)\n",
    "        need = m\n",
    "\n",
    "        for right in range(n):\n",
    "            if s[right] in cnt:                     # counter的单独用法？耗时长？需要优化？\n",
    "                if cnt[s[right]] > 0: #\n",
    "                    need -= 1\n",
    "                cnt[s[right]] -= 1\n",
    "\n",
    "            left = right - m\n",
    "            if left >= 0:\n",
    "                if s[left] in cnt:\n",
    "                    if cnt[s[left]] >= 0: # 此时滑出窗口的字符ch对need有影响\n",
    "                        need += 1\n",
    "                    cnt[s[left]] += 1\n",
    "            \n",
    "            if need == 0:\n",
    "                res.append(left+1)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "        \n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        ans = []\n",
    "        s_len = len(s)\n",
    "        p_len = len(p)\n",
    "        if p_len > s_len:\n",
    "            return ans\n",
    "\n",
    "        s_count = [0] * 26\n",
    "        p_count = [0] * 26\n",
    "        for i in range(p_len):\n",
    "            s_count[ord(s[i]) - ord('a')] += 1\n",
    "            p_count[ord(p[i]) - ord('a')] += 1\n",
    "        if s_count == p_count:\n",
    "            ans.append(0)\n",
    "        left, right = 0, p_len\n",
    "        while right < s_len:\n",
    "            print(s[right])\n",
    "            s_count[ord(s[left]) - ord('a')] -= 1\n",
    "            s_count[ord(s[right]) - ord('a')] += 1\n",
    "            left += 1\n",
    "            right += 1\n",
    "            if s_count == p_count:\n",
    "                ans.append(left)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        dic1,dic2=Counter(),Counter(p)\n",
    "        l,r,val=0,0,0\n",
    "        result=[]\n",
    "        while r< len(s):\n",
    "            c=s[r]\n",
    "            r+=1\n",
    "            if  c in dic2:\n",
    "                dic1[c]+=1\n",
    "                if dic1[c]==dic2[c]:\n",
    "                    val+=1\n",
    "            if val==len(dic2):result.append(l)\n",
    "            while r-l >= len(p):\n",
    "                \n",
    "                d=s[l]\n",
    "                l+=1\n",
    "                if d in dic2: \n",
    "                    if dic1[d]==dic2[d] :\n",
    "                        val-=1\n",
    "                    dic1[d]-=1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def is_same_dict(a, b):\n",
    "    flag = True\n",
    "    for key in a:\n",
    "        if a[key] != b[key]:\n",
    "            flag = False\n",
    "    return flag\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        start = 0\n",
    "        p_num = Counter(p)\n",
    "        p_len = len(p)\n",
    "\n",
    "        if p_len > len(s):\n",
    "            return []\n",
    "\n",
    "        char_dict = defaultdict(int)\n",
    "        while start < p_len:\n",
    "            char_dict[s[start]] += 1\n",
    "            start += 1\n",
    "        result = []\n",
    "        if is_same_dict(p_num, char_dict):\n",
    "            result.append(0)\n",
    "\n",
    "        \n",
    "        while start < len(s):\n",
    "            char_dict[s[start]] += 1\n",
    "            char_dict[s[start - p_len]] -= 1\n",
    "            if is_same_dict(p_num, char_dict):\n",
    "                result.append(start - p_len + 1)\n",
    "\n",
    "            start += 1\n",
    "        return result  \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        n_p = len(p)\n",
    "        n_s = len(s)\n",
    "        if n_p > n_s:\n",
    "            return []\n",
    "        need = n_p\n",
    "        ans = []\n",
    "        cnt = collections.Counter(p)\n",
    "        for right, c in enumerate(s):\n",
    "            if c in cnt:\n",
    "                if cnt[c] > 0 :\n",
    "                    need -= 1\n",
    "                cnt[c] -= 1\n",
    "            \n",
    "            left = right-n_p+1\n",
    "            if need == 0 :\n",
    "                ans.append(left)\n",
    "            if left >= 0 :\n",
    "                ch = s[left]\n",
    "                if ch in cnt:\n",
    "                    if cnt[ch] >= 0:\n",
    "                        need += 1\n",
    "                    cnt[ch] += 1\n",
    "                \n",
    "            \n",
    "        return ans\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        # 固定长度为 len(p) 的滑动窗口；结果存l\n",
    "        # 每个窗口统计字母出现次数\n",
    "        # 符合要求即 p字典 == 窗口字典\n",
    "\n",
    "        result = []\n",
    "\n",
    "        if len(p) > len(s):\n",
    "            return result\n",
    "\n",
    "        from collections import Counter\n",
    "        target_map = Counter(p)\n",
    "        # 初始化滑动窗口\n",
    "        l,r = 0,len(p)-1\n",
    "        window_map = Counter(s[l:r])\n",
    "\n",
    "        while r < len(s):\n",
    "            # 加入当前的值\n",
    "            window_map[s[r]] += 1\n",
    "            # 符合要求的记录\n",
    "            if window_map == target_map:\n",
    "                result.append(l)\n",
    "\n",
    "            # 移动窗口\n",
    "            window_map[s[l]] -= 1\n",
    "            l+=1\n",
    "            r+=1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        need = {}\n",
    "        win = {}\n",
    "        for w in p:\n",
    "            if w not in need:\n",
    "                need[w] = 1\n",
    "                win[w] = 0\n",
    "            else:\n",
    "                need[w] += 1\n",
    "        \n",
    "        l, r = 0, 0\n",
    "        res = []\n",
    "        v = 0\n",
    "\n",
    "        while r < n:\n",
    "            c = s[r]\n",
    "            r += 1\n",
    "            if c in need:\n",
    "                win[c] += 1\n",
    "                if win[c] == need[c]:\n",
    "                    v += 1\n",
    "            \n",
    "            while r-l >= len(p):\n",
    "                if v == len(need):\n",
    "                    res.append(l)\n",
    "                \n",
    "                d = s[l]\n",
    "                l += 1\n",
    "                if d in need:\n",
    "                    if win[d] == need[d]:\n",
    "                        v -= 1\n",
    "                    win[d] -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        n, m = len(s), len(p)\n",
    "        cur, target = Counter(), Counter(p)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            cur[s[i]] += 1\n",
    "            if i >= m - 1:\n",
    "                if cur == target:\n",
    "                    ans.append(i - m + 1)\n",
    "                cur[s[i - m + 1]] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        s_len, p_len = len(s), len(p)\n",
    "        \n",
    "        if s_len < p_len:\n",
    "            return []\n",
    "\n",
    "        ans = []\n",
    "        s_count = [0] * 26\n",
    "        p_count = [0] * 26\n",
    "        for i in range(p_len):\n",
    "            s_count[ord(s[i]) - ord('a')] += 1\n",
    "            p_count[ord(p[i]) - ord('a')] += 1\n",
    "\n",
    "        if s_count == p_count:\n",
    "            ans.append(0)\n",
    "\n",
    "        for i in range(s_len - p_len):\n",
    "            s_count[ord(s[i]) - ord('a')] -= 1\n",
    "            s_count[ord(s[i + p_len]) - ord('a')] += 1\n",
    "            \n",
    "            if s_count == p_count:\n",
    "                ans.append(i + 1)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        n, m = len(s), len(p)\n",
    "        target = Counter(p)\n",
    "        ans = []\n",
    "        for i in range(m, n + 1):\n",
    "            if Counter(s[i - m : i]) == target:\n",
    "                ans.append(i - m)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        s_len, p_len = len(s), len(p)\n",
    "        \n",
    "        if s_len < p_len:\n",
    "            return []\n",
    "\n",
    "        ans = []\n",
    "        s_count = [0] * 26\n",
    "        p_count = [0] * 26\n",
    "        for i in range(p_len):\n",
    "            s_count[ord(s[i]) - 97] += 1\n",
    "            p_count[ord(p[i]) - 97] += 1\n",
    "\n",
    "        if s_count == p_count:\n",
    "            ans.append(0)\n",
    "\n",
    "        for i in range(s_len - p_len):\n",
    "            s_count[ord(s[i]) - 97] -= 1\n",
    "            s_count[ord(s[i + p_len]) - 97] += 1\n",
    "            \n",
    "            if s_count == p_count:\n",
    "                ans.append(i + 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        need = {}\n",
    "        win = {}\n",
    "        for w in p:\n",
    "            if w not in need:\n",
    "                need[w] = 1\n",
    "                win[w] = 0\n",
    "            else:\n",
    "                need[w] += 1\n",
    "        \n",
    "        l, r = 0, 0\n",
    "        v = 0\n",
    "        res = []\n",
    "        while r < n:\n",
    "            c = s[r]\n",
    "            r += 1\n",
    "\n",
    "            if c in need:\n",
    "                win[c] += 1\n",
    "                if win[c] == need[c]:\n",
    "                    v += 1\n",
    "            \n",
    "            while r - l >= len(p):\n",
    "                if v == len(need):\n",
    "                    res.append(l)\n",
    "                \n",
    "                d = s[l]\n",
    "                l += 1\n",
    "\n",
    "                if d in need:\n",
    "                    if need[d] == win[d]:\n",
    "                        v -= 1\n",
    "                    win[d] -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        s_len,p_len=len(s),len(p)\n",
    "        if s_len<p_len:\n",
    "            return []\n",
    "        ans=[]\n",
    "        s_count=[0]*26#26个字母，小写字母\n",
    "        p_count=[0]*26\n",
    "        for i in range(p_len):\n",
    "            s_count[ord(s[i])-97]+=1\n",
    "            p_count[ord(p[i])-97]+=1\n",
    "        \n",
    "        if s_count==p_count:\n",
    "            ans.append(0)\n",
    "        \n",
    "        for i in range(s_len-p_len):\n",
    "            s_count[ord(s[i])-97]-=1\n",
    "            s_count[ord(s[i+p_len])-97]+=1\n",
    "\n",
    "            if s_count==p_count:\n",
    "                ans.append(i+1)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        s_len, p_len = len(s), len(p)\n",
    "        \n",
    "        if s_len < p_len:\n",
    "            return []\n",
    "\n",
    "        ans = []\n",
    "        s_count = [0] * 26\n",
    "        p_count = [0] * 26\n",
    "        for i in range(p_len):\n",
    "            s_count[ord(s[i]) - 97] += 1\n",
    "            p_count[ord(p[i]) - 97] += 1\n",
    "\n",
    "        if s_count == p_count:\n",
    "            ans.append(0)\n",
    "\n",
    "        for i in range(s_len - p_len):\n",
    "            s_count[ord(s[i]) - 97] -= 1\n",
    "            s_count[ord(s[i + p_len]) - 97] += 1\n",
    "            \n",
    "            if s_count == p_count:\n",
    "                ans.append(i + 1)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        n, m = len(s), len(p)\n",
    "        res = []\n",
    "        if n < m: return res\n",
    "        arr1, arr2 = [0] * 26, [0] * 26\n",
    "        for i in range(m):\n",
    "            arr1[ord(p[i]) - ord('a')] += 1\n",
    "            arr2[ord(s[i]) - ord('a')] += 1\n",
    "        for j in range(m, n):\n",
    "            if arr1 == arr2:\n",
    "                res.append(j - m)\n",
    "            arr2[ord(s[j - m]) - ord('a')] -= 1\n",
    "            arr2[ord(s[j]) - ord('a')] += 1\n",
    "        if arr1 == arr2: res.append(n - m)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        need = defaultdict(int)\n",
    "        for tmp_p in p:\n",
    "            need[tmp_p] += 1\n",
    "        l = r = 0\n",
    "        window = defaultdict(int)\n",
    "        n = len(s)\n",
    "        m = len(p)\n",
    "        res = []\n",
    "        while r < n:\n",
    "            window[s[r]] += 1\n",
    "            if r -l + 1 < m:\n",
    "                r += 1\n",
    "            else:\n",
    "                if window == need:\n",
    "                    res.append(l)\n",
    "                r += 1\n",
    "                window[s[l]] -= 1\n",
    "                if window[s[l]] == 0:\n",
    "                    del window[s[l]]\n",
    "                l += 1\n",
    "        return res\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def is_same_dict(a, b):\n",
    "    flag = True\n",
    "    for key in a:\n",
    "        if a[key] != b[key]:\n",
    "            flag = False\n",
    "            break\n",
    "    return flag\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        start = 0\n",
    "        p_num = Counter(p)\n",
    "        p_len = len(p)\n",
    "\n",
    "        if p_len > len(s):\n",
    "            return []\n",
    "\n",
    "        char_dict = defaultdict(int)\n",
    "        while start < p_len:\n",
    "            char_dict[s[start]] += 1\n",
    "            start += 1\n",
    "        result = []\n",
    "        if is_same_dict(p_num, char_dict):\n",
    "            result.append(0)\n",
    "\n",
    "        \n",
    "        while start < len(s):\n",
    "            char_dict[s[start]] += 1\n",
    "            char_dict[s[start - p_len]] -= 1\n",
    "            if is_same_dict(p_num, char_dict):\n",
    "                result.append(start - p_len + 1)\n",
    "\n",
    "            start += 1\n",
    "        return result  \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter, defaultdict\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        if len(s) < len(p):\n",
    "            return []\n",
    "        b = Counter(p)\n",
    "        a = defaultdict(int)\n",
    "        for i in range(len(p)):\n",
    "            a[s[i]] += 1\n",
    "        \n",
    "        ans = []\n",
    "        if a == b:\n",
    "            ans.append(0)\n",
    "        for i in range(len(p),len(s)):\n",
    "            a[s[i-len(p)]] -= 1\n",
    "            if a[s[i-len(p)]] == 0:\n",
    "                a.pop(s[i-len(p)])\n",
    "            a[s[i]] += 1\n",
    "            if a == b:\n",
    "                ans.append(i-len(p)+1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        res=[]\n",
    "        temp=set(p)\n",
    "        flag={i:0 for i in temp}\n",
    "        count={i:0 for i in temp}\n",
    "        for i in range(len(p)):\n",
    "            flag[p[i]]+=1\n",
    "        i=0\n",
    "        s_len=len(s)\n",
    "        p_len=len(p)\n",
    "        while i<s_len-p_len+1:\n",
    "            count={i:0 for i in temp}\n",
    "            for j in range(i,i+len(p)):\n",
    "                if s[j] not in temp:\n",
    "                    i=j\n",
    "                    break\n",
    "                else:\n",
    "                    count[s[j]]+=1\n",
    "            if list(count.values())==list(flag.values()):\n",
    "                res.append(i)\n",
    "            i+=1\n",
    "\n",
    "            # for char in s[i:i+len(p)]:\n",
    "            #     if char not in temp:\n",
    "            #         break\n",
    "            #     else:\n",
    "            #         count[char]+=1\n",
    "            # if list(count.values())==list(flag.values()):\n",
    "            #     res.append(i)\n",
    "\n",
    "\n",
    "        # for i in range(len(s)-len(p)+1):\n",
    "        #     count={i:0 for i in temp}\n",
    "        #     # print(s[i:i+len(p)])\n",
    "        #     for char in s[i:i+len(p)]:\n",
    "        #         if char not in temp:\n",
    "        #             break\n",
    "        #         else:\n",
    "        #             count[char]+=1\n",
    "        #     if list(count.values())==list(flag.values()):\n",
    "        #         res.append(i)\n",
    "            # print(flag,list(flag.values()))\n",
    "            # print(count,list(count.values()))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        windows = {}\n",
    "        need = {}\n",
    "        for c in p:\n",
    "            need[c] = need.get(c, 0) + 1\n",
    "\n",
    "        right = left = valid = 0\n",
    "        res = []\n",
    "        while right < len(s):\n",
    "            c = s[right]\n",
    "            right += 1\n",
    "\n",
    "            if c in need:\n",
    "                windows[c] = windows.get(c, 0) + 1\n",
    "\n",
    "                if need[c] == windows[c]:\n",
    "                    valid += 1\n",
    "            if right - left >= len(p):\n",
    "                if valid == len(need):\n",
    "                    res.append(left)\n",
    "\n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                if d in need:\n",
    "                    if need[d] == windows[d]:\n",
    "                        valid -= 1\n",
    "                    windows[d] -= 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        need, window = defaultdict(int), defaultdict(int)\n",
    "        for c in p:\n",
    "            need[c] += 1\n",
    "        left, right = 0, 0\n",
    "        \n",
    "        valid = 0\n",
    "        ans = []\n",
    "        while right < len(s):\n",
    "            c = s[right]\n",
    "            right += 1\n",
    "\n",
    "            if c in need:\n",
    "                window[c] += 1\n",
    "                if window[c] == need[c]:\n",
    "                    valid += 1\n",
    "            \n",
    "            if right - left == len(p):\n",
    "                if valid == len(need):\n",
    "                    ans.append(left)\n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                if d in need:\n",
    "                    if window[d] == need[d]:\n",
    "                        valid -= 1\n",
    "                    window[d] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        n, m = len(s), len(p)\n",
    "        res = []\n",
    "        if n < m: return res\n",
    "        arr1, arr2 = [0] * 26, [0] * 26\n",
    "        for i in range(m):\n",
    "            arr1[ord(p[i]) - ord('a')] += 1\n",
    "            arr2[ord(s[i]) - ord('a')] += 1\n",
    "        for j in range(m, n):\n",
    "            if arr1 == arr2:\n",
    "                res.append(j - m)\n",
    "            arr2[ord(s[j - m]) - ord('a')] -= 1\n",
    "            arr2[ord(s[j]) - ord('a')] += 1\n",
    "        if arr1 == arr2: res.append(n - m)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        l1, l2 = len(s), len(p)\n",
    "        if l2>l1:\n",
    "            return []\n",
    "        rs = []\n",
    "        d1, d2 = defaultdict(int), defaultdict(int)\n",
    "\n",
    "        for ch in p:\n",
    "            d2[ch] += 1\n",
    "        \n",
    "        for ch in s[:l2]:\n",
    "            d1[ch] += 1\n",
    "        \n",
    "        if d1==d2:\n",
    "            rs.append(0)\n",
    "        \n",
    "        for ch_idx in range(l2, l1):  # 右滑\n",
    "            left_ch = s[ch_idx-l2]\n",
    "            d1[left_ch] -= 1\n",
    "            if d1[left_ch] == 0:\n",
    "                del d1[left_ch]\n",
    "            \n",
    "            cur_ch = s[ch_idx]\n",
    "            d1[cur_ch] += 1\n",
    "\n",
    "            if d1==d2:\n",
    "                rs.append(ch_idx-l2+1)\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        n_p = len(p)\n",
    "        n_s = len(s)\n",
    "        if n_p > n_s:\n",
    "            return []\n",
    "        need = n_p\n",
    "        ans = []\n",
    "        cnt = collections.Counter(p)\n",
    "        for right, c in enumerate(s):\n",
    "            if c in cnt:\n",
    "                if cnt[c] > 0 :\n",
    "                    need -= 1\n",
    "                cnt[c] -= 1\n",
    "            \n",
    "            left = right-n_p\n",
    "            if left >= 0 :\n",
    "                ch = s[left]\n",
    "                if ch in cnt:\n",
    "                    if cnt[ch] >= 0:\n",
    "                        need += 1\n",
    "                    cnt[ch] += 1\n",
    "                \n",
    "            if need == 0 :\n",
    "                ans.append(left+1)\n",
    "        return ans\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def is_same_dict(a, b):\n",
    "    flag = True\n",
    "    for key in a:\n",
    "        if a[key] != b[key]:\n",
    "            flag = False\n",
    "    return flag\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        start = 0\n",
    "        p_num = Counter(p)\n",
    "        p_len = len(p)\n",
    "\n",
    "        if p_len > len(s):\n",
    "            return []\n",
    "\n",
    "        char_dict = defaultdict(int)\n",
    "        while start < p_len:\n",
    "            char_dict[s[start]] += 1\n",
    "            start += 1\n",
    "        result = []\n",
    "        if is_same_dict(p_num, char_dict):\n",
    "            result.append(0)\n",
    "\n",
    "        \n",
    "        while start < len(s):\n",
    "            char_dict[s[start]] += 1\n",
    "            char_dict[s[start - p_len]] -= 1\n",
    "            if is_same_dict(p_num, char_dict):\n",
    "                result.append(start - p_len + 1)\n",
    "\n",
    "            start += 1\n",
    "        return result  \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        if len(s) < len(p):\n",
    "            return []\n",
    "        indices = []\n",
    "        s_freq = self.get_ch_freq(s[:len(p)])\n",
    "        p_freq = self.get_ch_freq(p)\n",
    "        if self.is_equal(s_freq, p_freq):\n",
    "            indices.append(0)\n",
    "        for i in range(len(p), len(s)):\n",
    "            s_freq[ord(s[i]) - ord(\"a\")] += 1\n",
    "            s_freq[ord(s[i - len(p)]) - ord(\"a\")] -= 1\n",
    "            if self.is_equal(s_freq, p_freq):\n",
    "                indices.append(i - len(p) + 1)\n",
    "        return indices\n",
    "\n",
    "    def get_ch_freq(self, s: str) -> List[int]:\n",
    "        freq = [0] * 26\n",
    "        for c in s:\n",
    "            freq[ord(c) - ord(\"a\")] += 1\n",
    "        return freq\n",
    "\n",
    "    def is_equal(self, freq1: List[int], freq2: List[int]) -> bool:\n",
    "        for i in range(len(freq1)):\n",
    "            if freq1[i] != freq2[i]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        len_s, len_p = len(s), len(p)\n",
    "        if len_s < len_p:\n",
    "            return []\n",
    "\n",
    "        lookup = defaultdict(int)\n",
    "        cnt = len_p\n",
    "        for c in p:\n",
    "            lookup[c] += 1\n",
    "        \n",
    "        for i in range(len_p):\n",
    "            lookup[s[i]] -= 1\n",
    "            if lookup[s[i]] >= 0:\n",
    "                cnt -= 1\n",
    "        \n",
    "        i,j,res = 0, len_p-1, []\n",
    "        while j < len_s:\n",
    "            if cnt == 0:\n",
    "                res.append(i)\n",
    "            j += 1\n",
    "            if j == len_s:\n",
    "                break\n",
    "            \n",
    "            lookup[s[j]] -= 1\n",
    "            if lookup[s[j]] >= 0:\n",
    "                cnt -= 1\n",
    "\n",
    "            lookup[s[i]] += 1\n",
    "            if lookup[s[i]] > 0:\n",
    "                cnt += 1\n",
    "            i += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        n_p = len(p)\n",
    "        n_s = len(s)\n",
    "        if n_p > n_s:\n",
    "            return []\n",
    "        need = n_p\n",
    "        ans = []\n",
    "        cnt = collections.Counter(p)\n",
    "        for right, c in enumerate(s):\n",
    "            if c in cnt:\n",
    "                if cnt[c] > 0 :\n",
    "                    need -= 1\n",
    "                cnt[c] -= 1\n",
    "            \n",
    "            left = right-n_p+1\n",
    "            if need == 0 :\n",
    "                ans.append(left)\n",
    "            if left >= 0 :\n",
    "                ch = s[left]\n",
    "                if ch in cnt:\n",
    "                    if cnt[ch] >= 0:\n",
    "                        need += 1\n",
    "                    cnt[ch] += 1\n",
    "                \n",
    "            \n",
    "        return ans\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter, defaultdict\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        # return [index]\n",
    "        if len(s) < len(p):\n",
    "            return []\n",
    "        \n",
    "        dic_p = defaultdict(int)\n",
    "        for each in p:\n",
    "            dic_p[each] += 1\n",
    "            \n",
    "        dic_s = defaultdict(int)\n",
    "        for i in range(len(p)):\n",
    "            dic_s[s[i]] += 1\n",
    "        ans = []\n",
    "        if dic_s == dic_p:\n",
    "            ans.append(0)\n",
    "        for i in range(len(p),len(s)):\n",
    "            \n",
    "            dic_s[s[i - len(p)]] -= 1\n",
    "            if dic_s[s[i - len(p)]] == 0:\n",
    "                dic_s.pop(s[i - len(p)])\n",
    "            dic_s[s[i]] += 1\n",
    "            if dic_s == dic_p:\n",
    "                ans.append(i - len(p)+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        need = defaultdict(int)\n",
    "        for t in p:\n",
    "            need[t] += 1\n",
    "        window = defaultdict(int)\n",
    "        n = len(s)\n",
    "        m = len(p)\n",
    "        res = []\n",
    "        if n < m:\n",
    "            return res\n",
    "        l = r = 0\n",
    "        while r < n:\n",
    "            if r < m:\n",
    "                window[s[r]] += 1\n",
    "                r += 1\n",
    "            else:\n",
    "                if window == need:\n",
    "                    res.append(l)\n",
    "                window[s[r]] += 1\n",
    "                window[s[l]] -= 1\n",
    "                if window[s[l]] == 0:\n",
    "                    del window[s[l]]\n",
    "                l += 1\n",
    "                r += 1\n",
    "        if window == need:\n",
    "            res.append(l)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        sLen = len(s)\n",
    "        res = []\n",
    "        if sLen == 0:\n",
    "            return res \n",
    "        pLen = len(p)\n",
    "\n",
    "        window = collections.Counter()\n",
    "        pattern = collections.Counter(p)\n",
    "\n",
    "        sCount = 0\n",
    "        pCount = len(pattern.keys()) # p中unique字符的个数\n",
    "        \n",
    "        left, right = 0, 0\n",
    "        while right < sLen:\n",
    "            if pattern[s[right]] > 0:\n",
    "                window[s[right]] += 1\n",
    "                if window[s[right]] == pattern[s[right]]: #如果 s 中某个字符的频率与 p 中一样，sCount 加 1  \n",
    "                    sCount += 1\n",
    "            right += 1\n",
    "\n",
    "            while pCount == sCount:\n",
    "                if right - left == pLen:\n",
    "                    res.append(left)\n",
    "                if pattern[s[left]] > 0:\n",
    "                    window[s[left]] -= 1\n",
    "                    if window[s[left]] < pattern[s[left]]:\n",
    "                        sCount -= 1\n",
    "                left += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        result = []\n",
    "        if len(p) > len(s):\n",
    "            return []\n",
    "\n",
    "        # 初始化两个数组，用于存储每个字母出现次数\n",
    "        arr1, arr2 = [0] * 26, [0] * 26\n",
    "        for i in range(len(p)):\n",
    "            arr1[ord(p[i]) - ord('a')] += 1\n",
    "            arr2[ord(s[i]) - ord('a')] += 1\n",
    "        if arr1 == arr2:\n",
    "            result.append(0)\n",
    "\n",
    "\n",
    "        # 初始化定长滑动窗口(左开右闭，故答案存左index+1)\n",
    "        l,r = 0,len(p)\n",
    "\n",
    "        while r < len(s):\n",
    "            # 右指针当前值 count+1\n",
    "            # 左指针当前值 count-1\n",
    "            arr2[ord(s[r]) - ord('a')] += 1\n",
    "            arr2[ord(s[l]) - ord('a')] -= 1\n",
    "            if arr1 == arr2:\n",
    "                result.append(l + 1)\n",
    "            l+=1\n",
    "            r+=1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        ans = []\n",
    "        s_len = len(s)\n",
    "        p_len = len(p)\n",
    "        if p_len > s_len:\n",
    "            return ans\n",
    "        p_map = defaultdict(int)\n",
    "        s_map = defaultdict(int)\n",
    "\n",
    "        def check():\n",
    "            for k, v in p_map.items():\n",
    "                if v != s_map.get(k, 0):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        for i in range(p_len):\n",
    "            p_map[p[i]] += 1\n",
    "            s_map[s[i]] += 1\n",
    "\n",
    "        left, right = 0, p_len\n",
    "        if check():\n",
    "            ans.append(left)\n",
    "\n",
    "        while right < s_len:\n",
    "            s_map[s[right]] += 1\n",
    "            s_map[s[left]] -= 1\n",
    "            if check():\n",
    "                ans.append(left + 1)\n",
    "            left += 1\n",
    "            right += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        arr1 = [0]*26\n",
    "        arr2 = [0]*26\n",
    "        if len(s)<len(p):\n",
    "            return []\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(len(p)):\n",
    "            arr1[ord(s[i])-ord('a')] += 1\n",
    "            arr2[ord(p[i])-ord('a')] += 1\n",
    "        \n",
    "        if arr1 == arr2:\n",
    "            ans.append(0)\n",
    "        for i in range(len(p),len(s)):\n",
    "            arr1[ord(s[i])-ord('a')] += 1\n",
    "            arr1[ord(s[i-len(p)])-ord('a')] -= 1\n",
    "\n",
    "            if arr1 == arr2:\n",
    "                ans.append(i-len(p)+1)\n",
    "\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        need = defaultdict(int)\n",
    "        for t in p:\n",
    "            need[t] += 1\n",
    "        window = defaultdict(int)\n",
    "        n = len(s)\n",
    "        m = len(p)\n",
    "        res = []\n",
    "        if n < m:\n",
    "            return res\n",
    "        l = r = 0\n",
    "        while r < n:\n",
    "            if r < m:\n",
    "                window[s[r]] += 1\n",
    "                r += 1\n",
    "            else:\n",
    "                if window == need:\n",
    "                    res.append(l)\n",
    "                window[s[r]] += 1\n",
    "                window[s[l]] -= 1\n",
    "                if window[s[l]] == 0:\n",
    "                    del window[s[l]]\n",
    "                l += 1\n",
    "                r += 1\n",
    "        if window == need:\n",
    "            res.append(l)\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        res = []\n",
    "\n",
    "        # 记录p中的各个字符出现次数\n",
    "        char2cnt = {}\n",
    "        for i in range(len(p)):\n",
    "            char2cnt[p[i]] = char2cnt.get(p[i], 0) + 1\n",
    "        \n",
    "        # s[left...right]中的字符都在p中出现过，且频次不超过p的频次\n",
    "        left = 0\n",
    "        for right in range(len(s)):\n",
    "            while left <= right and char2cnt.get(s[right], 0) <= 0:\n",
    "                if s[left] in char2cnt:\n",
    "                    char2cnt[s[left]] += 1\n",
    "                left += 1\n",
    "            \n",
    "            if s[right] in char2cnt:\n",
    "                char2cnt[s[right]] -= 1\n",
    "            \n",
    "            if right - left + 1 == len(p) and sum(char2cnt.values()) == 0:\n",
    "                res.append(left)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        if True:\n",
    "            if len(s)<len(p): return []\n",
    "\n",
    "            results = []\n",
    "            from collections import Counter\n",
    "            p_counter = Counter(p)\n",
    "            results = [i for i in range(len(s)-len(p)+1) if Counter(s[i:i+len(p)]) == p_counter]\n",
    "            return results\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        elif False:\n",
    "            from collections import Counter\n",
    "\n",
    "            if len(s) < len(p):\n",
    "                return []\n",
    "            \n",
    "            results = []\n",
    "            p_counter = Counter(p) \n",
    "            p_len = len(p)       \n",
    "\n",
    "            def check_str(s1):\n",
    "                return Counter(s1) == p_counter\n",
    "\n",
    "            for i in range(len(s)-p_len +1):\n",
    "                if check_str(s[i: i+p_len]):\n",
    "                    results.append(i)\n",
    "\n",
    "            return results\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        left = cnt = 0\n",
    "        curr = {}\n",
    "        c = Counter(p)\n",
    "        res = []\n",
    "        for right in  range(len(s)):\n",
    "            if s[right] not in c:\n",
    "                cnt = 0\n",
    "                curr = {}\n",
    "                left = right + 1\n",
    "            else:\n",
    "                curr[s[right]] = curr[s[right]] + 1 if s[right] in curr else 1\n",
    "                cnt += 1\n",
    "                while curr[s[right]] > c[s[right]]:\n",
    "                    if s[left] in curr:\n",
    "                        curr[s[left]] -= 1\n",
    "                        if curr[s[left]] == 0:\n",
    "                            del curr[s[left]]\n",
    "                        cnt -= 1\n",
    "                    left += 1\n",
    "                if cnt == len(p):\n",
    "                    res.append(left)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        l = len(p)\n",
    "        if len(s) < l:\n",
    "            return []\n",
    "        ans = []\n",
    "\n",
    "        c = collections.Counter(p)\n",
    "        for i in range(l):\n",
    "            if s[i] in c:\n",
    "                c[s[i]] -= 1\n",
    "            if set(c.values()) == {0}:\n",
    "                ans.append(i - l + 1)\n",
    "        \n",
    "        cur = l\n",
    "        while cur < len(s):\n",
    "            if s[cur] in c:\n",
    "                c[s[cur]] -= 1\n",
    "            if s[cur-l] in c:\n",
    "                c[s[cur-l]] += 1\n",
    "            \n",
    "            if set(c.values()) == {0}:\n",
    "                ans.append(cur - l + 1)\n",
    "            cur += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        need = defaultdict(int)\n",
    "        window = defaultdict(int)\n",
    "        for tmp_p in p:\n",
    "            need[tmp_p] += 1\n",
    "        l = 0\n",
    "        n = len(s)\n",
    "        m = len(p)\n",
    "        res = []\n",
    "        if n < m:\n",
    "            return res\n",
    "        for r in range(m):\n",
    "            window[s[r]] += 1\n",
    "        r = m - 1\n",
    "        while r + 1 < n:\n",
    "            if dict(window) == dict(need):\n",
    "                res.append(l)\n",
    "            r += 1\n",
    "            window[s[r]] += 1\n",
    "            window[s[l]] -= 1\n",
    "            if window[s[l]] == 0:\n",
    "                del window[s[l]]\n",
    "            l += 1\n",
    "        if dict(window) == dict(need):\n",
    "            res.append(l)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        m,n  = len(p),len(s)\n",
    "        res = []\n",
    "        counts = [0] *26\n",
    "        if m>n:\n",
    "            return []\n",
    "        for i in range(m):\n",
    "            counts[ord(s[i]) -ord('a')] -=1\n",
    "            counts[ord(p[i]) -ord('a')] +=1\n",
    "        if  all(x ==0 for  x in counts):\n",
    "            res.append(0)\n",
    "        for  j in range(m,n):\n",
    "            counts[ord(s[j]) - ord('a')] -=1\n",
    "            counts[ord(s[j-m])-ord('a')] +=1\n",
    "            if all(x==0 for x in counts):\n",
    "                res.append(j-m+1)\n",
    "        return  res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findAnagrams(self, s, p):\n",
    "\t\tn = len(p)\n",
    "\t\tif n > len(s):\n",
    "\t\t\treturn []\n",
    "\t\tcnt = {}\n",
    "\t\tfor char in p:\n",
    "\t\t\tcnt[char] = cnt.get(char, 0) + 1\n",
    "\t\tdiff = n\n",
    "\t\tfor i in range(n):\n",
    "\t\t\tcnt[s[i]] = cnt.get(s[i], 0) - 1\n",
    "\t\t\tdiff += 1 if cnt[s[i]] < 0 else -1\n",
    "\t\tans = [0] if diff == 0 else []\n",
    "\t\tfor i in range(n, len(s)):\n",
    "\t\t\tcnt[s[i]] = cnt.get(s[i], 0) - 1\n",
    "\t\t\tdiff += 1 if cnt[s[i]] < 0 else -1\n",
    "\t\t\tcnt[s[i - n]] += 1\n",
    "\t\t\tdiff -= 1 if cnt[s[i - n]] <= 0 else -1\n",
    "\t\t\tif diff == 0:\n",
    "\t\t\t\tans.append(i - n + 1)\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        need = {}\n",
    "        windows = {}\n",
    "        left = right = 0\n",
    "        valid = 0\n",
    "        res = []\n",
    "        for c in p:\n",
    "            need[c] = need.get(c, 0) + 1\n",
    "\n",
    "        while right < len(s):\n",
    "            c = s[right]\n",
    "            right += 1\n",
    "\n",
    "            if c in need:\n",
    "                windows[c] = windows.get(c, 0) + 1\n",
    "                if windows[c] == need[c]:\n",
    "                    valid += 1\n",
    "            \n",
    "            while right - left >= len(p):\n",
    "                if valid == len(need):\n",
    "                    res.append(left)\n",
    "                \n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                if d in need:\n",
    "                    if windows[d] == need[d]:\n",
    "                        valid -= 1\n",
    "                    windows[d] -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, str2: str, str1: str) -> List[int]:\n",
    "        \n",
    "        res=[]\n",
    "        dic={}\n",
    "        len1=len(str1)\n",
    "        len2=len(str2)\n",
    "        if len2<len1:\n",
    "            return []\n",
    "        for i in range(len1):\n",
    "            if dic.get(str1[i]):\n",
    "                dic[str1[i]]+=1\n",
    "            else:\n",
    "                dic[str1[i]]=1\n",
    "            if dic.get(str2[i]):\n",
    "                dic[str2[i]]-=1\n",
    "            else:\n",
    "                dic[str2[i]]=-1\n",
    "        if self.allzero(dic):\n",
    "            res.append(0)\n",
    "        for i in range(1,len2-len1+1):\n",
    "            k=str2[i-1]\n",
    "            dic[str2[i-1]]+=1\n",
    "            if dic.get(str2[i+len1-1]):\n",
    "                dic[str2[i+len1-1]]-=1\n",
    "            else:\n",
    "                dic[str2[i+len1-1]]=-1\n",
    "            if self.allzero(dic):\n",
    "                res.append(i)\n",
    "        return res\n",
    "\n",
    "\n",
    "    def allzero(self,dic):\n",
    "        for i in dic:\n",
    "            if dic[i]!=0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        m=len(p)\n",
    "        target=dict()\n",
    "        for i in p:\n",
    "            target[i]=target.get(i,0)+1\n",
    "        res=[]\n",
    "        n=len(s)\n",
    "        if m>n: return res\n",
    "        cur=dict()\n",
    "        for i in range(m-1):\n",
    "            cur[s[i]]=cur.get(s[i],0)+1\n",
    "        \n",
    "        # ans=[]\n",
    "        for i in range(m-1,n):\n",
    "            cur[s[i]]=cur.get(s[i],0)+1\n",
    "            if cur==target: res.append(i-m+1)\n",
    "            cur[s[i-m+1]]-=1\n",
    "            if cur[s[i-m+1]]==0:\n",
    "                del cur[s[i-m+1]]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str, ord=ord) -> List[int]:\n",
    "        count_p = [0] * 26\n",
    "        count_w = [0] * 26\n",
    "        order_a = ord('a')\n",
    "        for c in p:\n",
    "            count_p[ord(c) - order_a] += 1\n",
    "\n",
    "        length_p = len(p)\n",
    "        anagrams = []\n",
    "        orders_s = [ord(c) - order_a for c in s]\n",
    "        append = anagrams.append\n",
    "        last = None\n",
    "        left = 0\n",
    "        for right, ro in enumerate(orders_s):\n",
    "            if right >= length_p:\n",
    "                lo = orders_s[left]\n",
    "                if lo == ro and last == left:\n",
    "                    left += 1\n",
    "                    last = left\n",
    "                    append(last)\n",
    "                    continue\n",
    "                left += 1\n",
    "                count_w[lo] -= 1\n",
    "            count_w[ro] += 1\n",
    "            if count_p[ro] and count_w == count_p:\n",
    "                last = left\n",
    "                append(last)\n",
    "        return anagrams\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "\n",
    "        p_dict=Counter(p)\n",
    "        \n",
    "        dict_t=Counter(s[:len(p)])\n",
    "\n",
    "        res=[]\n",
    "\n",
    "        if p_dict==dict_t:\n",
    "            res.append(0)\n",
    "        \n",
    "        #print(res)\n",
    "\n",
    "\n",
    "        for i in range(1,len(s)-len(p)+1):\n",
    "            j=i+len(p)-1\n",
    "            if dict_t.get(s[i-1])==1:\n",
    "                del dict_t[s[i-1]]\n",
    "            elif dict_t[s[i-1]]:\n",
    "                dict_t[s[i-1]]-=1\n",
    "            \n",
    "            dict_t[s[j]]=dict_t.get(s[j],0)+1\n",
    "\n",
    "            if p_dict==dict_t:\n",
    "                res.append(i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        ans = []\n",
    "        m = len(p)\n",
    "        if m > len(s):\n",
    "            return ans\n",
    "        cnt = [0] * 26\n",
    "        for ch in p:\n",
    "            cnt[ord(ch)-97] += 1\n",
    "        \n",
    "        need = sum(c != 0 for c in cnt)\n",
    "        nums = [ord(ch)-97 for ch in s]\n",
    "        for i, x in enumerate(nums):\n",
    "            cnt[x] -= 1\n",
    "            if cnt[x] == 0:\n",
    "                need -= 1\n",
    "            if i-m >= 0:\n",
    "                x = nums[i-m]\n",
    "                if cnt[x] == 0:\n",
    "                    need += 1\n",
    "                cnt[x] += 1\n",
    "            if need == 0:\n",
    "                ans.append(i-m+1)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        arr1, arr2, lg = [0]*26, [0]*26, len(p)\n",
    "\n",
    "        if len(s) < len(p):\n",
    "            return []\n",
    "        for i in range(lg):\n",
    "            arr1[ord(p[i]) - ord('a')] += 1\n",
    "            arr2[ord(s[i]) - ord('a')] += 1\n",
    "\n",
    "        ans = []\n",
    "        j = i + 1\n",
    "        while j < len(s):\n",
    "            if arr1 == arr2:\n",
    "                ans.append(j-lg)\n",
    "            arr2[ord(s[j]) - ord('a')] += 1\n",
    "            arr2[ord(s[j-lg]) - ord('a')] -= 1\n",
    "            j+= 1\n",
    "\n",
    "        if arr1 == arr2:\n",
    "            ans.append(j-lg)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
